package com.ds.heap.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/10/5 11:25
 */
public class Num347_TopKFrequent {
    class Pairs{
        int key;
        int value;
        Pairs(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        //把键值对入hashMap中
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        //建立小根堆，覆写优先级队列的Comparator接口，根据Pairs的value大小建立小根堆
        Queue<Pairs> queue = new PriorityQueue<>((o1,o2) -> o1.value - o2.value);
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if(queue.size()<k){
                queue.offer(new Pairs(entry.getKey(),entry.getValue()));
            }else{
                int peek = queue.peek().value;
                if(entry.getValue()>peek){
                    queue.poll();
                    queue.offer(new Pairs(entry.getKey(),entry.getValue()));
                }
            }
        }
        //限制K的大小，TopK
        int[] ret = new int[k];
        int i = 0;
        while (!queue.isEmpty()){
            ret[i++] = queue.poll().key;
        }
        return ret;
    }
}
